package a08_回溯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * <p>
 * a03_组合优化复习1
 * </p>
 *
 * @author flyduck
 * @since 2024/12/30
 */
public class a03_组合优化复习1 {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();

        traversal(resultList, path, n, k, 1);
        return resultList;
    }

    //1,2,3,4,5,6,7,8,9,10 n=10，k=5，
    //假设path现在里面有2个
    //那么i从1开始可以
    //那么i从2开始可以
    //那么i从3开始可以
    //...
    //那么i从8开始可以

    //还差的元素5-3=3
    //n - (k-path.size()) + 1

    public void traversal(List<List<Integer>> resultList,
                          LinkedList<Integer> path,
                          int n,
                          int k,
                          int startIdx){
        if (path.size() == k) {
            resultList.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIdx; i <= n - (k-path.size()) + 1; i++) {
            path.add(i);
            traversal(resultList, path, n, k, i + 1);
            path.removeLast();
        }
    }
}
